import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class L40 {
    public static void main(String[] args) {
        int[] candidates = {1, 2, 2, 2, 5};
        int target = 5;
        List<List<Integer>> lists = new Solution().combinationSum2(candidates, target);
        for (List<Integer> list : lists) {
            System.out.println(list.toString());
        }

    }

//    static class Solution {
//        List<List<Integer>> result = new ArrayList<>();
//        LinkedList<Integer> tmp = new LinkedList<>();
//
//
//        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//            Arrays.sort(candidates);
//            int left = 0;
//            int right = candidates.length - 1;
//
//            while (left < right) {
//                if (candidates[right] > target) {
//                    right--;
//                    continue;
//                } else if (candidates[right] == target) {
//                    tmp.add(candidates[right]);
//                    result.add(new LinkedList<>(tmp));
//                    tmp.removeLast();
//                } else {
//                    tmp.add(candidates[right]);
//                    target -= candidates[right];
//
//                }
//                if (candidates[left] > target) {
//                    break;
//                } else if (candidates[left] == target) {
//                    tmp.add(candidates[left]);
//                    result.add(new LinkedList<>(tmp));
//                    tmp.removeLast();
//                } else {
//                    tmp.add(candidates[left]);
//                    target -= candidates[left];
//                }
//
//                right--;
//                left++;
//            }
//            return result;
//        }
//    }


    static class Solution {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> tmp = new LinkedList<>();
        boolean[] used;


        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            int index = 0;
            used = new boolean[candidates.length];
            Arrays.fill(used, false);
            Arrays.sort(candidates);
            backTracking(candidates, target, index);
            return result;
        }

        private void backTracking(int[] candidates, int target, int index) {
            if (target == 0) {
                result.add(new LinkedList<>(tmp));
                return;
            } else if (target < 0) {
                return;
            }

            for (int i = index; i < candidates.length; i++) {
                if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i] = true;
                tmp.add(candidates[i]);
                target -= candidates[i];
                backTracking(candidates, target, i + 1);
                used[i] = false;
                target += candidates[i];
                tmp.removeLast();
            }
        }
    }
}
